package algorithme;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Random;
import java.util.Set;

public class Bench {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Bench b = new Bench();
		float optimal;
		int nbsommets = 1500;
		long duree;
		while (nbsommets < 1805) {
			Graphe graphe = b.grapheGeneration(nbsommets, 5, 20);
			// Graphe graphe = b.grapheTest();
			System.out.println("Test du graphe :");
			// System.out.println(graphe);
			duree = b.testerAlgo(graphe, new Kruskal());
			System.out.println("Kruskal," + nbsommets + "," + graphe.nbAretes()
					+ "," + duree);
			duree = b.testerAlgo(graphe, new Boruvka());
			System.out.println("Boruvka," + nbsommets + "," + graphe.nbAretes()
					+ "," + duree);
			duree = b.testerAlgo(graphe, new RandomBoruvka());
			System.out.println("Random Boruvka," + nbsommets + "," + graphe.nbAretes()
					+ "," + duree);
			//duree = b.testerAlgo(graphe, new Rouxov_Sivadov(3));
			System.out.println("Rouxov_Sivadov," + nbsommets + "," + graphe.nbAretes()
					+ "," + duree);
			optimal = b.optimalite(new Kruskal(), graphe);
			System.out.println("Test d'optimalité de kruskal : " + optimal);
			optimal = b.optimalite(new Boruvka(), graphe);
			System.out.println("Test d'optimalité de boruvka : " + optimal);
			optimal = b.optimalite(new RandomBoruvka(), graphe);
			System.out.println("Test d'optimalité de RandomBoruvka : " + optimal);
			//optimal = b.optimalite(new Rouxov_Sivadov(3), graphe);
			System.out.println("Test d'optimalité de Rouxov_Sivadov(N=3) : " + optimal);
			nbsommets += 50;
		}
	}

	private long testerAlgo(Graphe graphe, Algorithme algo) {
		// System.out.println("Essai de "+algo.getName());
		long debut = System.currentTimeMillis();
		algo.appliquer(graphe);
		long duree = System.currentTimeMillis() - debut;
		// System.out.println("#Temps de calcul : "+duree+"
		// ms\n******************************\n");
		return duree;
	}

	private Graphe grapheGeneration(int nbSommets, int densite, int maxPoids) {
		Random rand = new Random();
		Collection<Arete> aretes = new ArrayList<Arete>();
		for (int i = 0; i < nbSommets - 1; i++) {
			aretes.add(new Arete(i, i + 1, rand.nextInt(maxPoids) + 1));
			for (int j = i + 2; j < nbSommets; j++) {
				if (rand.nextInt(100) < densite)
					aretes.add(new Arete(i, j, rand.nextInt(maxPoids) + 1));
			}
		}
		return new Graphe(aretes);
	}

	private Graphe grapheTest() {
		Graphe graphe = new Graphe();
		graphe.ajouterArete(new Arete(0, 1, 6));
		graphe.ajouterArete(new Arete(0, 3, 13));
		graphe.ajouterArete(new Arete(1, 2, 12));
		graphe.ajouterArete(new Arete(1, 3, 19));
		graphe.ajouterArete(new Arete(2, 3, 4));
		graphe.ajouterArete(new Arete(2, 4, 10));
		graphe.ajouterArete(new Arete(3, 4, 5));
		return graphe;
	}

	private float optimalite(Algorithme algo, Graphe graphe) {
		Algorithme krus = new Kruskal();
		Graphe acpmAlgo = algo.appliquer(graphe);
		Graphe acpmKrus = krus.appliquer(graphe);

		Set<Integer> sommets = graphe.getSommets();
		int poidsKrus = 0;
		for (Arete a : acpmKrus.getAretes())
			poidsKrus += a.getPoids();

		Set<Integer> sommetsAlgo = acpmAlgo.getSommets();
		int poidsAlgo = 0;
		for (Arete a : acpmAlgo.getAretes())
			poidsAlgo += a.getPoids();
		System.out.println(algo.getName()+" poids : "+poidsAlgo);
		if (!sommetsAlgo.containsAll(sommets)) {
			System.err.println("Il manque des sommets !");
			return 0.f;
		}
		if (poidsAlgo > poidsKrus)
			return poidsKrus / poidsAlgo;
		return poidsKrus / poidsAlgo;
	}
}
